package com.hj.sort;

import java.util.Arrays;

/**
 * @author hj
 * @Date 2022/1/5
 * @Description: 直接插入排序
 */
public class InsertionSort {

    public void insertionSort(int[] array) {
        if (null == array) {
            return;
        }
        // 类似冒泡排序算法,遍历
        for (int i = 0; i < array.length; i++) {
            // 核心是从局部有序.到整体有序
            // 当前基准元素
            int temp = array[i];
            int j;
            for (j = i; j > 0 && array[j - 1] > temp; j--) {
                // 下一个元素比基准元素大,下一个元素向后移动
                array[j] = array[j - 1];
            }
            // 最后比较当前元素和基准元素大小
            if (array[j] > temp) {
                array[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        InsertionSort insertionSort = new InsertionSort();
        int[] array = {5, 9, 125, 6, 85, 97, 45, 3, 25, 64, 36, 98, 103, 45, 12, 35};
        insertionSort.insertionSort(array);
        System.out.println(Arrays.toString(array));
    }

}
